from __future__ import annotations
from typing import List, Any, Iterator, Tuple

class Node(object):
    def __init__(self, value : int) -> None:
        self.value : int = value
        self.next : Node = None
        #raise ValueError
     
class LinkedList(object):
    def __init__(self, *args : Tuple) -> None:
        self.head : Node = Node(None)
        self.element_num : int = 0
        if len(args)!=0 :
           self.create_method3(args[0]) #get the first params
    
    def add_front(self,data : int) -> None:
        node : Node = Node(data)
        if self.head.value is None and self.element_num ==0 :
            self.head = node
        else:
            node.next = self.head.next
            self.head.next = node
        
    def add_tail(self,data) -> None:
        node : Node = Node(data)
        if self.head.value is None and self.element_num ==0 :
            self.head = node
        else:
            p : Node = self.head
            while p.next is not None:
                p = p.next
            p.next = node
        
    def create_method2(self,values : List[int]) -> Node:
        if len(values)==0 :
            return None
        self.head = Node(values[0])
        for i, item in enumerate(values[1:]):
            self.add_front(item)
        return self.head
    
    def create_method3(self,values : List[int]) -> Node:
        if len(values)==0 :
            return None
        self.head = Node(values[0])
        for i, item in enumerate(values[1:]):
            self.add_tail(item)
        return self.head
                    
    def create_method1(self,values : List[int]) -> Node:
        if len(values)==0 :
            return None
        self.head = Node(values[0])
        p : Node = self.head
        for i, item in enumerate(values[1:]):
            node = Node(item)
            p.next = node
            p = p.next
        return self.head
        
    def view(self) -> None:
        p : Node = self.head
        element_list : List[Node[Any]] = list()
        while p is not None:
            element_list.append(p.value)
            p = p.next
        
        print(element_list)
            
    def length(self) -> int:
        p : Node = self.head
        while p is not None:
            p = p.next
            self.element_num += 1
        return self.element_num 
        
    def reverse_method1(self) -> None:
        if self.element_num <= 1 :
            return
        
        if self.element_num ==2 :
            p : Node = self.head.next
            self.head.next = None
            p.next = self.head       
            self.head = p
            return
        
        if self.element_num >=3 :
            q : Node = self.head.next
            p : Node = q.next
            t : Node = self.head
            while p :
                self.head.next = p
                q.next = t
                
                #update element index position
                t = q
                q = p
                p = p.next
                
            self.head.next = None
            q.next = t
            self.head = q
               
    def reverse_method2(self) -> None:
        cur : Node = self.head
        pre : Node = None
        post: Node = self.head.next
        
        while post is not None:
            cur.next = pre
            
            #update element index position
            pre = cur
            cur = post
            post = post.next
        
        cur.next = pre
        self.head = cur
         
def merge(list1 : LinkedList, list2 : LinkedList):
    p : Node = list1.head
    q : Node = list2.head

    if p is None:
        return list1.head       
    if q is None:
        return list2.head 
         
    new_head = Node(None)
    new_tail = new_head
    while p is not None or q is not None:
        if p is not None and q is not None:
            if p.value < q.value:
                new_tail.next = p
                p = p.next
                new_tail = new_tail.next  
            else:
                new_tail.next = q
                q = q.next
                new_tail = new_tail.next       
        if p is None and q is not None:
            new_tail.next = q
            q = q.next
            new_tail = new_tail.next 
        if q is None and p is not None:
            new_tail.next = p
            p = p.next
            new_tail = new_tail.next
               
    return new_head.next    
    
if __name__ == "__main__":
    linked_list1 = LinkedList([1])
    linked_list1.view()        
    print(linked_list1.length())
    linked_list1.reverse_method2()
    linked_list1.view()  
    
    
    linked_list2 = LinkedList()
    linked_list2.add_tail(1)
    linked_list2.add_tail(3)
    linked_list2.add_tail(5)
    linked_list2.add_tail(7)
    linked_list2.add_tail(9)
    linked_list2.view()        
    print(linked_list2.length())
    linked_list2.reverse_method2()
    linked_list2.view()

    linked_list3 = LinkedList([1,2,3,4,5])
    linked_list4 = LinkedList([7,8,9])
    head  = merge(linked_list3, linked_list4)
    #linked_list.view()
    #print(linked_list.len())  
 